package com.qch.edu.lagou.homework;

/**
 * @Author qch
 * @Date 2021/7/23
 * 0-1背包问题 O（i*j）
很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，
需要参与挖掘的工人人数也不 同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人 来挖掘…… 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要 求用程序求出，
要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
 * （注意：每个物品只有一件，也就是每个物品只能选择0件或者1件分析）
 *
 * dp方程：
 * 如果：1）可以选这金矿j>w[i]
 *          1.不选：dp[i][j]=dp[i-1][j]
 *          2.选了：：dp[i][j]=v[i]+dp[i-1,j-w[i]]
 *          两者取价值最大的数 :Max(dp[i-1][j],v[i]+dp[i-1,j-w[i]])
 *       2）不可以选这金矿j<w[i]
 *           则：dp[i][j]=dp[i-1][j]
 */
public class Kuangshi {
    /**
     * 计算最大价值
     * @param values 金矿的重量数数组
     * @param worker 工人量数组
     * @param max 最多工人
     * @return
     */
    public static int MaxVaue(int[] values,int[] worker,int max)
    {
        if(values==null||values.length==0)
        {
            return 0;
        }
        if(worker==null||worker.length==0)
        {
            return 0;
        }
        if(worker.length!=values.length||max<0)
        {
            return 0;
        }
        //dp数组
        int[][]dp=new int[values.length+1][max+1];
        for (int i = 1; i <=values.length; i++) {
            for (int j=1;j<=max;j++){
                //选择的金矿所需工人数超过最大工人
                if(j<worker[i-1])
                {
                    //不能选择该金矿
                    dp[i][j]=dp[i-1][j];
                }else {
                    //可选，可不选
                    //上轮最大黄金重量
                    int proValue=dp[i-1][j];
                    int curValue=values[i-1]+dp[i-1][j-worker[i-1]];
                    dp[i][j]=Math.max(proValue,curValue);
   }
            }

        }
        return dp[values.length][max];
    }

    public static void main(String[] args) {
        int[] values = {500,200,100,300,1720};
        int[] workers = {5,3,2,4,10};
        int max = 10;
        System.out.println(MaxVaue(values, workers, max));
    }
}
